//输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 
//
// 
//
// 例如，给出 
//
// 前序遍历 preorderorder = [3,9,20,15,7]
//中序遍历 inorder = [9,3,15,20,7] 
//
// 返回如下的二叉树： 
//
//     3
//   / \
//  9  20
//    /  \
//   15   7 
//
// 
//
// 限制： 
//
// 0 <= 节点个数 <= 5000 
//
// 
//
// 注意：本题与主站 105 题重复：https://leetcode-cn.com/problems/construct-binary-tree-from-
//preorderorder-and-inorder-traversal/ 
// Related Topics 树 递归 
// 👍 182 👎 0


package com.yun.leetcode.editor.cn;

import java.util.Arrays;

public class ZhongJianErChaShuLcof {
    public static void main(String[] args) {
        Solution solution = new ZhongJianErChaShuLcof().new Solution();
    }
//leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public TreeNode buildTree(int[] preorderorder, int[] inorder) {
            // 前序，根左右
            // 中序，左根右
            // 后序，左右根
            // 自己开始思路错误，非想着拆分数组一步到位

            return reBuildTree(preorderorder, 0, preorderorder.length-1, inorder, 0, inorder.length-1);

        }

        private TreeNode reBuildTree(int[] preorder, int pStart, int pEnd, int[] inorder, int iStart, int iEnd) {
            if (pStart > pEnd || iStart > iEnd) {
                return null;
            }
            int rootValue = preorder[pStart];
            TreeNode root = new TreeNode(rootValue);
            // 从iStart -> iEnd去循环
            // 去分开中序遍历的根左元素和根右元素
            // 这里如果不用等号，那最后一个元素是根的话，就处理不到了
            for (int i = iStart; i <= iEnd; i++) {

                if (inorder[i] == rootValue) {
                    // 左子树重建，
                    // 自己写的错的
//                root.left = reBuildTree(preorder, pStart + 1, , inorder, iStart + 1, i-1);
                    // 问题1. 不知道左子树的前序遍历截止，前序遍历根左右，中序遍历左根右，i在走中序遍历，i-iStart是不是表示左子树的长度
                    // 问题2. 左子树的中序遍历起始是错的。 原因：中序遍历左根右，左侧也是左子树的部分，所以不用加一
//                root.right = reBuildTree(preorder, ,, inorder, i+1, iEnd):
                    // 尝试写出右子树的界限
                    // porder, pStart+i-iStart+1,pEnd,    iorder, iStart+i+1, iEnd
                    // 问题3. 右子树的中序起始是错的。 真菜，你上面用i的时候，要算i几位，所以你用i-start。这里直接第i位置了，你还减，难道要从头算吗。
                    root.left = reBuildTree(preorder, pStart + 1, pStart + i - iStart, inorder, iStart, i - 1);
                    root.right = reBuildTree(preorder, pStart + i - iStart + 1, pEnd, inorder, i + 1, iEnd);
                    break;
                }
            }
            return root;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)


    // 尝试再写边界,写出来，厉害
    public TreeNode reBuildTree(int[] preOrder, int pStart, int pEnd, int[] inOrder, int iStart, int iEnd) {

        if (pStart < pEnd || iStart < iEnd) {
            return null;
        }
        TreeNode root = new TreeNode(preOrder[pStart]);
        for (int i = iStart; i <= iEnd ; i++) {
            // i是当前根的位置
            if (inOrder[i] == preOrder[pStart]) {
                root.left = reBuildTree(preOrder, pStart + 1 , pStart + i- iStart ,inOrder, iStart, i-1);
                root.right = reBuildTree(preOrder, pStart+i-iStart+1, pEnd ,inOrder, i+1, iEnd);
            }
        }
        return root;
    }
}